package main

import (
	"fmt"
	"math"
	"sort"
)

func main() {
	//nums := []int{3,4,1,2,2,2,2}
	nums := []int{2, 2, 3, 3, 3, 4}
	fmt.Println(deleteAndEarn(nums))
}

func deleteAndEarn(nums []int) int {
	base := make(map[int]int)
	for _, v := range nums {
		base[v] += v
	}
	keys := make([]int, 1)
	for k := range base {
		keys = append(keys, k)
	}
	sort.Ints(keys)
	dpTab := make([]int, len(keys))
	dpTab[0] = base[keys[0]]
	if keys[1]-keys[0] == 1 {
		dpTab[1] = base[keys[1]]
	} else {
		dpTab[1] = base[keys[1]] + base[keys[0]]
	}

	if keys[2]-keys[1] == 1 {
		dpTab[2] = base[keys[2]] + dpTab[0]
	} else {
		dpTab[2] = int(math.Max(float64(dpTab[1]), float64(dpTab[0]))) + base[keys[2]]
	}

	for i := 3; i < len(keys); i++ {
		if keys[i]-keys[i-1] == 1 {
			dpTab[i] = int(math.Max(float64(dpTab[i-2]), float64(dpTab[i-3]))) + base[keys[i]]
		} else {
			dpTab[i] = int(math.Max(float64(dpTab[i-1]), float64(dpTab[i-2]))) + base[keys[i]]
		}
	}
	return int(math.Max(float64(dpTab[len(dpTab)-1]), float64(dpTab[len(dpTab)-2])))
}

func fastSort(nums []int) {
	if len(nums) < 2 {
		return
	}
	mid := nums[0]
	l, r := 1, len(nums)-1
	for l <= r {
		for ; l <= r && nums[l] <= mid; l++ {
		}
		for ; l <= r && nums[r] > mid; r-- {
		}
		if l < r {
			nums[l], nums[r] = nums[r], nums[l]
			l++
			r--
		}
	}
	nums[0], nums[r] = nums[r], nums[0]
	fastSort(nums[:r])
	fastSort(nums[l:])
}
